#include "cryptonacl.h"

#include <limits>

#define sv static inline void
#define si static inline int

extern "C" void randombytes(u8 *,u64);


template<class T, int N> using C = crypto_array<T, N>;

typedef C<u8,4> B4;
typedef C<u8,8> B8;
typedef C<u8,16> B16;
typedef C<u8,64> B64;

typedef i64 gf[16];


template<int I>
struct intT
{
    static  constexpr int res = I;
};


template<int I, int End, int Step>
struct Unroll
{
    template<typename Lambda>
    static inline void step(Lambda func)
    {
        func(intT<I>());
        Unroll<I+Step, End, Step>::step(func);
    }
};
template<int End>
struct Unroll<End, End, +1> {
    template<typename Lambda>
    static inline void step(Lambda) {}
};
template<>
struct Unroll<0, 0, -1> {
    template<typename Lambda>
    static inline void step(Lambda func) { func(intT<0>()); }
};


#define FORu(i,n) \
    static_assert(std::numeric_limits<int>::max() >= n,"Overflow in FORu loop"); \
    Unroll<0, n, +1>::step([&](auto I) { \
        constexpr int i = decltype(I)::res;(void)I;
#define ENDu }})

#define ROFu(i,n) \
    static_assert(std::numeric_limits<int>::max() >= n,"Overflow in ROFu loop"); \
    Unroll<n, 0, -1>::step([&](auto I) { \
        constexpr int i = decltype(I)::res;(void)I;
#define ENDr }})

// much smaller bin size
//#define SLOW

#ifdef SLOW
#undef FORu
#define FORu(i,n) for (int i = 0; i < n; ++i)
#undef ENDu
#define ENDu }
#endif

#ifdef SLOW
#undef ROFu
#define ROFu(i,n) for (int i = n; i >= 0; --i)
#undef ENDr
#define ENDr }
#endif

#define FORn(i,n) \
    for (decltype(n) i = 0;i < n;++i)



template<int I, int End>
struct UnrollCheck
{
    template<typename Lambda, class A>
    static inline void step(Lambda func, A a)
    {
        func(intT<I>(), intT<A::Size>());
        UnrollCheck<I+1, End>::step(func, a);
    }
};
template<int End>
struct UnrollCheck<End, End> {
    template<typename Lambda, class A>
    static inline void step(Lambda, A) {}
};
#define FOR(i,n) \
    static_assert(std::numeric_limits<int>::max() >= n,"Overflow in FOR loop"); \
    UnrollCheck<0, n>::step([&](auto I, auto Size) { \
        constexpr int i = decltype(I)::res;(void)I; \
        static_assert(i < decltype(Size)::res, "Out-of-bound access");

template<int I, int End, int J>
struct UnrollCheck2
{
    template<typename Lambda, class A>
    static inline void step(Lambda func, A a)
    {
        func(intT<I>(), intT<J>(), intT<A::Size>());
        UnrollCheck2<I+1, End, J>::step(func, a);
    }
};
template<int End, int J>
struct UnrollCheck2<End, End, J> {
    template<typename Lambda, class A>
    static inline void step(Lambda, A) {}
};
#define FOR2(i,n,j) \
    static_assert(std::numeric_limits<int>::max() >= n,"Overflow in FOR2 loop"); \
    UnrollCheck2<0, n, j>::step([&](auto I, auto J, auto Size) { \
        constexpr int i = decltype(I)::res;(void)I; \
        constexpr int j = decltype(J)::res;(void)J; \
        static_assert(decltype(I)::res < decltype(Size)::res, "Out-of-bound access");

#define CHKSIZE(x) static_assert((x) < decltype(Size)::res, "Out-of-bound access")


static constexpr u8
_0[16] = {0},
_9[32] = {9};
static constexpr gf
gf0 = {0},
gf1 = {1},
_121665 = {0xDB41,1},
D = {0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203},
D2 = {0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406},
X = {0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169},
Y = {0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666},
I = {0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83};

static inline u32 L32(u32 x,int c)
{
    return (x << c) | ((x&0xffffffff) >> (32 - c));
}

static inline u32 ld32(const B4 &x)
{
    u32 u = x[3];
    u = (u<<8)|x[2];
    u = (u<<8)|x[1];
    return (u<<8)|x[0];
}

static inline u64 dl64(const B8 &x)
{
    u64 u=0;
    FOR(i,8) {
        u=(u<<8)|x[i];
    }},x);
    return u;
}

sv st32(u8 *x,u32 u)
{
    FORu(i,4) {
        x[i] = u;
        u >>= 8;
    ENDu;
}

sv ts64(u8 *x,u64 u)
{
    ROFu(i,7) {
        x[i] = u;
        u >>= 8;
    ENDr;
}

template<int N>
static inline int crypto_verify(const C<u8,N> &x, const C<u8,N> &y)
{
    u32 d = 0;
    FORn(i,N) {
        d |= x[i]^y[i];
    }
    return (1 & ((d - 1) >> 8)) - 1;
}

template<bool H>
sv core(C<u8,H?32:64> &out, const C<u8,H?24:16> &in, const Key &k, const B4 &c)
{
    C<u32,4> t;
    C<u32,16> w,x,y;

    FOR(i,4) {
        x[5*i] = ld32(c+4*i);
        x[1+i] = ld32(k+4*i);
        x[6+i] = ld32(in+4*i);
        x[11+i] = ld32(k+16+4*i);
        CHKSIZE(5*i);
        CHKSIZE(11+i);
    }},x);

    FOR(i,16) {
        y[i] = x[i];
    }},y);

    FORu(i,20) {
        (void)i;
        FOR(j,4) {
            FOR2(m,4,j) {
                t[m] = x[(5*j+4*m)%16];
                CHKSIZE((5*3+4*m)%16);
            }},x);
            t[1] ^= L32(t[0]+t[3], 7);
            t[2] ^= L32(t[1]+t[0], 9);
            t[3] ^= L32(t[2]+t[1],13);
            t[0] ^= L32(t[3]+t[2],18);

            FOR2(m,4,j) {
                w[4*j+(j+m)%4] = t[m];
                CHKSIZE(4*3+(3+m)%4);
            }}, w);
        }},w);
        FOR(m,16) {
            x[m] = w[m];
        }},x);
    ENDu;

    if (H) {
        FOR(i,16) {
            x[i] += y[i];
        }},x);
        FOR(i,4) {
            x[5*i] -= ld32(c+4*i);
            x[6+i] -= ld32(in+4*i);
            CHKSIZE(5*i);
            CHKSIZE(6+i);
        }},x);
        FOR(i,4) {
            st32(out.p()+4*i,x[5*i]);
            st32(out.p()+16+4*i,x[6+i]);
            CHKSIZE(5*i);
            CHKSIZE(6+i);
        }},x);
    } else {
        FOR(i,16) {
            st32(out.p() + 4 * i,x[i] + y[i]);
        }},x);
    }
}

si crypto_core_salsa20(B64 &out, const B16 &in, const Key &k, const B4 &c)
{
    core<false>(out,in,k,c);
    return 0;
}

si crypto_core_hsalsa20(Key &out, const Nonce &in, const Key &k, const B4 &c)
{
    core<true>(out,in,k,c);
    return 0;
}

static constexpr u8 sigma_data[16] = {'e','x','p','a','n','d',' ','3','2','-','b','y','t','e',' ','k'};
static const B4 sigma = B4::wrap(sigma_data);

typedef C<u8,Nonce::Size-16> SalsaNonce;

si crypto_stream_salsa20_xor(Message &cmsg, const Message &msg, const SalsaNonce &n, const Key &k)
{
    B16 z;
    B64 x;
    u64 b = msg.n;
    if (!b) return 0;
    FOR(i,16) {
        z[i] = 0;
    }},z);
    FOR(i,8) {
        z[i] = n[i];
    }},z);
    u8* m = msg.p;
    u8* c = cmsg.p;
    while (b >= 64) {
        crypto_core_salsa20(x,z,k,sigma);
        FOR(i,64) {
            c[i] = (m?m[i]:0) ^ x[i];
        }},x);
        u64 u = 1;
        for (int i = 8; i < 16; ++i) {
            u += (u32) z[i];
            z[i] = u;
            u >>= 8;
        }
        b -= 64;
        c += 64;
        if (m) m += 64;
    }
    if (b) {
        crypto_core_salsa20(x,z,k,sigma);
        FORn(i,b) {
            c[i] = (m?m[i]:0) ^ x[i];
        }
    }
    return 0;
}


si crypto_stream_salsa20(Message &c, const SalsaNonce &n, const Key& k)
{
    return crypto_stream_salsa20_xor(c,Message(),n,k);
}

int crypto_stream(Key &x, const Nonce &n, const Key& k)
{
    Key s;
    crypto_core_hsalsa20(s,n,k,sigma);
    auto c = x.t0();
    return crypto_stream_salsa20(c,n+16,s);
}

si crypto_stream_xor(Message &c, const Message &m, const Nonce &n, const Key &k)
{
    Key s;
    crypto_core_hsalsa20(s,n,k,sigma);
    return crypto_stream_salsa20_xor(c,m,n+16,s);
}

sv add1305(C<u32,17>& h,const C<u32,17>& c)
{
    u32 u = 0;
    FOR(j,17) {
        u += h[j] + c[j];
        h[j] = u & 255;
        u >>= 8;
    }},h);
}

static constexpr u32 minusp_data[17] = { 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252 } ;
static const C<u32, 17> minusp = C<u32, 17>::wrap(minusp_data);

si crypto_onetimeauth(B16 &out,const Message& msg,const Key &k)
{
    u32 s;
    C<u32,17> x,r,h,c,g;

    FOR(j,17) {
        r[j]=h[j]=0;
    }},r);
    FOR(j,16) {
        r[j]=k[j];
    }},r);
    r[3]&=15;
    r[4]&=252;
    r[7]&=15;
    r[8]&=252;
    r[11]&=15;
    r[12]&=252;
    r[15]&=15;

    u8* m = msg.p;
    u64 n = msg.n;
    while (n > 0) {
        FOR(j,17) {
            c[j] = 0;
        }},c);
        u32 j;
        for (j = 0; (j < 16) && (j < n); ++j) {
            c[j] = m[j];
        }
        c[j] = 1;
        m += j;
        n -= j;
        add1305(h,c);
        FOR(i,17) {
            x[i] = 0;
            FOR2(j,17,i) {
                x[i] += h[j] * ((j <= i) ? r[i - j] : 320 * r[i + 17 - j]);
                CHKSIZE(((j <= i) ? i - j : i + 17 - j));
            }},x);
        }},x);
        FOR(i,17) {
            h[i] = x[i];
        }},x);
        u32 u = 0;
        FOR(j,16) {
            u += h[j];
            h[j] = u & 255;
            u >>= 8;
        }},h);
        u += h[16];
        h[16] = u & 3;
        u = 5 * (u >> 2);
        FOR(j,16) {
            u += h[j];
            h[j] = u & 255;
            u >>= 8;
        }},h);
        u += h[16];
        h[16] = u;
    }

    FOR(j,17) {
        g[j] = h[j];
    }},g);
    add1305(h,minusp);
    s = -(h[16] >> 7);
    FOR(j,17) {
        h[j] ^= s & (g[j] ^ h[j]);
    }},h);

    FOR(j,16) {
        c[j] = k[j + 16];
    }},c);
    c[16] = 0;
    add1305(h,c);
    FOR(j,16) {
        out[j] = h[j];
    }},h);
    return 0;
}

si crypto_onetimeauth_verify(const B16 &h,const Message &m, const Key &k)
{
    B16 x;
    crypto_onetimeauth(x,m,k);
    return crypto_verify(h,x);
}

int crypto_secretbox(Message &c, const Message &m, const Nonce &n, const Key &k)
{
    if (m.n < 32) return -1;
    crypto_stream_xor(c,m,n,k);
    auto x = B16::wrap(c.p+16);
    Key keyc = Key::wrap(c.p);
    crypto_onetimeauth(x,c+32,keyc);
    FORu(i,16) {
        c[i] = 0;
    ENDu;
    return 0;
}

int crypto_secretbox_open(Message &m, const Message &c, const Nonce &n, const Key &k)
{
    Key x;
    if (c.n < 32) return -1;
    crypto_stream(x,n,k);
    auto y = B16::wrap(c.p+16);
    if (crypto_onetimeauth_verify(y,c+32,x) != 0) return -1;
    crypto_stream_xor(m,c,n,k);
    FORu(i,32) {
        m[i] = 0;
    ENDu;
    return 0;
}

sv set25519(gf r, const gf a)
{
    FORu(i,16) {
        r[i]=a[i];
    ENDu;
}

sv car25519(gf o)
{
    u64 c;
    FORu(i,16) {
        o[i]+=(1LL<<16);
        c=o[i]>>16;
        o[(i+1)*(i<15)]+=c-1+37*(c-1)*(i==15);
        o[i]-=c<<16;
    ENDu;
}

sv sel25519(gf p,gf q,int b)
{
    i64 t,c=~(b-1);
    FORu(i,16) {
        t= c&(p[i]^q[i]);
        p[i]^=t;
        q[i]^=t;
    ENDu;
}

sv pack25519(Key &o,const gf n)
{
    int b;
    gf m,t;
    FORu(i,16) {
        t[i]=n[i];
    ENDu;
    car25519(t);
    car25519(t);
    car25519(t);
    FORu(j,2) {
        (void)j;
        m[0]=t[0]-0xffed;
        for(int i=1; i<15; i++) {
            m[i]=t[i]-0xffff-((m[i-1]>>16)&1);
            m[i-1]&=0xffff;
        }
        m[15]=t[15]-0x7fff-((m[14]>>16)&1);
        b=(m[15]>>16)&1;
        m[14]&=0xffff;
        sel25519(t,m,1-b);
    ENDu;
    FOR(i,16) {
        o[2*i]=t[i]&0xff;
        o[2*i+1]=t[i]>>8;
    }},o);
}

si neq25519(const gf a, const gf b)
{
    Key c, d;
    pack25519(c,a);
    pack25519(d,b);
    return crypto_verify(c,d);
}

static inline u8 par25519(const gf a)
{
    Key d;
    pack25519(d,a);
    return d[0]&1;
}

sv unpack25519(gf o, const Key& n)
{
    FOR(i,16) {
        o[i]=n[2*i]+((i64)n[2*i+1]<<8);
    }},n);
    o[15]&=0x7fff;
}

sv A(gf o,const gf a,const gf b)
{
    FORu(i,16) {
        o[i]=a[i]+b[i];
    ENDu;
}

sv Z(gf o,const gf a,const gf b)
{
    FORu(i,16) {
        o[i]=a[i]-b[i];
    ENDu;
}

sv M(gf o,const gf a,const gf b)
{
    C<i64,31> t;
    FOR(i,31) {
        t[i]=0;
    }},t);
    FOR(i,16) {
        FOR2(j,16,i) {
            t[i+j]+=a[i]*b[j];
            CHKSIZE(i+j);
        }},t);
    }},t);
    FOR(i,15) {
        t[i]+=38*t[i+16];
        CHKSIZE(i+16);
    }},t);
    FOR(i,16) {
        o[i]=t[i];
    }},t);
    car25519(o);
    car25519(o);
}

sv S(gf o,const gf a)
{
    M(o,a,a);
}

sv inv25519(gf o,const gf i)
{
    gf c;
    FORu(a,16) {
        c[a]=i[a];
    ENDu;
    ROFu(a,253) {
        S(c,c);
        if(a!=2&&a!=4) M(c,c,i);
    ENDr;
    FORu(a,16) {
        o[a]=c[a];
    ENDu;
}

sv pow2523(gf o,const gf i)
{
    gf c;
    FORu(a,16) {
        c[a]=i[a];
    ENDu;
    ROFu(a,250) {
        S(c,c);
        if(a!=1) M(c,c,i);
    ENDr;
    FORu(a,16) {
        o[a]=c[a];
    ENDu;
}

si crypto_scalarmult(Key &q, const Key &n, const Key &p)
{
    u8 z[32];
    C<i64,80> x;
    i64 r;
    gf a,b,c,d,e,f;
    FOR(i,31) {
        z[i]=n[i];
    }},n);
    z[31]=(n[31]&127)|64;
    z[0]&=248;
    unpack25519(x.p(),p);
    FOR(i,16) {
        b[i]=x[i];
        d[i]=a[i]=c[i]=0;
    }},x);
    a[0]=d[0]=1;
    ROFu(i,254) {
        r=(z[i>>3]>>(i&7))&1;
        sel25519(a,b,r);
        sel25519(c,d,r);
        A(e,a,c);
        Z(a,a,c);
        A(c,b,d);
        Z(b,b,d);
        S(d,e);
        S(f,a);
        M(a,c,a);
        M(c,b,e);
        A(e,a,c);
        Z(a,a,c);
        S(b,a);
        Z(c,d,f);
        M(a,c,_121665);
        A(a,a,d);
        M(c,c,a);
        M(a,d,f);
        M(d,b,x.p());
        S(b,e);
        sel25519(a,b,r);
        sel25519(c,d,r);
    ENDr;
    FOR(i,16) {
        x[i+16]=a[i];
        x[i+32]=c[i];
        x[i+48]=b[i];
        x[i+64]=d[i];
        CHKSIZE(i+64);
    }},x);
    const auto cxp = x.p();
    inv25519(x.p()+32,cxp+32);
    M(x.p()+16,cxp+16,cxp+32);
    pack25519(q,cxp+16);
    return 0;
}

si crypto_scalarmult_base(Key &q, const Key &n)
{
    Key __9 = Key::wrap(_9);
    return crypto_scalarmult(q, n, __9);
}

int crypto_box_keypair(Key* pk, Key* sk)
{
    randombytes(sk->p(),32);
    return crypto_scalarmult_base(*pk, *sk);
}

int crypto_box_beforenm(Key &k,const Key &y, const Key &x)
{
    Key s;
    crypto_scalarmult(s,x,y);
    auto __0 = Nonce::wrap(_0);
    return crypto_core_hsalsa20(k,__0,s,sigma);
}

int crypto_box_afternm(Message &c, const Message &m, const Nonce &n, const Key &k)
{
    return crypto_secretbox(c,m,n,k);
}

int crypto_box_open_afternm(Message &m, const Message &c,const Nonce &n,const Key &k)
{
    return crypto_secretbox_open(m,c,n,k);
}

int crypto_box(Message &c, const Message &m, const Nonce &n, const Key &y,const Key &x)
{
    Key k;
    crypto_box_beforenm(k,y,x);
    return crypto_box_afternm(c,m,n,k);
}

int crypto_box_open(Message &m, const Message &c, const Nonce &n, const Key &y, const Key &x)
{
    Key k;
    crypto_box_beforenm(k,y,x);
    return crypto_box_open_afternm(m,c,n,k);
}

static inline u64 R(u64 x,int c)
{
    return (x >> c) | (x << (64 - c));
}
static inline u64 Ch(u64 x,u64 y,u64 z)
{
    return (x & y) ^ (~x & z);
}
static inline u64 Maj(u64 x,u64 y,u64 z)
{
    return (x & y) ^ (x & z) ^ (y & z);
}
static inline u64 Sigma0(u64 x)
{
    return R(x,28) ^ R(x,34) ^ R(x,39);
}
static inline u64 Sigma1(u64 x)
{
    return R(x,14) ^ R(x,18) ^ R(x,41);
}
static inline u64 sigma0(u64 x)
{
    return R(x, 1) ^ R(x, 8) ^ (x >> 7);
}
static inline u64 sigma1(u64 x)
{
    return R(x,19) ^ R(x,61) ^ (x >> 6);
}

static constexpr u64 K[80] = {
    0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
    0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL, 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
    0xd807aa98a3030242ULL, 0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
    0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
    0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL, 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
    0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
    0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
    0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL, 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
    0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
    0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
    0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL, 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
    0xd192e819d6ef5218ULL, 0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
    0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
    0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL, 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
    0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
    0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
    0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
    0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
    0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
    0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL, 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
};

si crypto_hashblocks(B64 &x,const Message &msg, u64 n)
{
    C<u64,8> z,b,a;
    C<u64,16> w;

    FOR(i,8) {
        z[i] = a[i] = dl64(x + 8 * i);
    }},z);

    u8* m = msg.p;
    while (n >= 128) {
        FOR(i,16) {
            w[i] = dl64(B8::wrap(m) + 8 * i);
        }},w);

        FORu(i,80) {
            FOR(j,8) {
                b[j] = a[j];
            }},b);
            u64 t = a[7] + Sigma1(a[4]) + Ch(a[4],a[5],a[6]) + K[i] + w[i%16];
            b[7] = t + Sigma0(a[0]) + Maj(a[0],a[1],a[2]);
            b[3] += t;
            FOR(j,8) {
                a[(j+1)%8] = b[j];
                CHKSIZE((j+1)%8);
            }},a);
            if (i%16 == 15) {
                FOR(j,16) {
                    w[j] += w[(j+9)%16] + sigma0(w[(j+1)%16]) + sigma1(w[(j+14)%16]);
                    CHKSIZE((j+14)%16);
                }},w);
            }
        ENDu;

        FOR(i,8) {
            a[i] += z[i];
            z[i] = a[i];
        }},a);

        m += 128;
        n -= 128;
    }

    FOR(i,8) {
        ts64(x.p()+8*i,z[i]);
    }},z);

    return n;
}

static constexpr u8 iv[64] = {
    0x6a,0x09,0xe6,0x67,0xf3,0xbc,0xc9,0x08,
    0xbb,0x67,0xae,0x85,0x84,0xca,0xa7,0x3b,
    0x3c,0x6e,0xf3,0x72,0xfe,0x94,0xf8,0x2b,
    0xa5,0x4f,0xf5,0x3a,0x5f,0x1d,0x36,0xf1,
    0x51,0x0e,0x52,0x7f,0xad,0xe6,0x82,0xd1,
    0x9b,0x05,0x68,0x8c,0x2b,0x3e,0x6c,0x1f,
    0x1f,0x83,0xd9,0xab,0xfb,0x41,0xbd,0x6b,
    0x5b,0xe0,0xcd,0x19,0x13,0x7e,0x21,0x79
} ;

si crypto_hash(B64 &out,const Message &msg, u64 n)
{
    B64 h;
    C<u8,256> x;
    u64 b = n;

    FOR(i,64) {
        h[i] = iv[i];
    }},h);

    crypto_hashblocks(h,msg,n);
    u8* m = msg.p;
    m += n;
    n &= 127;
    m -= n;

    FOR(i,256) {
        x[i] = 0;
    }},x);
    FORn(i,n) {
        x[i] = m[i];
    }
    x[n] = 128;

    n = 256-128*(n<112);
    x[n-9] = b >> 61;
    ts64(x.p()+n-8,b<<3);
    crypto_hashblocks(h,x.t0(),n);

    FOR(i,64) {
        out[i] = h[i];
    }},out);

    return 0;
}

si crypto_hash(B64 &out, const Key &k)
{
    return crypto_hash(out, k.t0(), Key::Size);
}

sv add(gf p[4],gf q[4])
{
    gf a,b,c,d,t,e,f,g,h;

    Z(a, p[1], p[0]);
    Z(t, q[1], q[0]);
    M(a, a, t);
    A(b, p[0], p[1]);
    A(t, q[0], q[1]);
    M(b, b, t);
    M(c, p[3], q[3]);
    M(c, c, D2);
    M(d, p[2], q[2]);
    A(d, d, d);
    Z(e, b, a);
    Z(f, d, c);
    A(g, d, c);
    A(h, b, a);

    M(p[0], e, f);
    M(p[1], h, g);
    M(p[2], g, f);
    M(p[3], e, h);
}

sv cswap(gf p[4],gf q[4],u8 b)
{
    FORu(i,4) {
        sel25519(p[i],q[i],b);
    ENDu;
}

sv pack(Key &r,gf p[4])
{
    gf tx, ty, zi;
    inv25519(zi, p[2]);
    M(tx, p[0], zi);
    M(ty, p[1], zi);
    pack25519(r, ty);
    r[31] ^= par25519(tx) << 7;
}

sv scalarmult(gf p[4],gf q[4], const B64 &s)
{
    set25519(p[0],gf0);
    set25519(p[1],gf1);
    set25519(p[2],gf1);
    set25519(p[3],gf0);
    ROFu(i,255) {
        u8 b = (s[i/8]>>(i&7))&1;
        cswap(p,q,b);
        add(q,p);
        add(p,p);
        cswap(p,q,b);
    ENDr;
}

sv scalarbase(gf p[4], const B64 &s)
{
    gf q[4];
    set25519(q[0],X);
    set25519(q[1],Y);
    set25519(q[2],gf1);
    M(q[3],X,Y);
    scalarmult(p,q,s);
}

si crypto_sign_keypair(Key &pk, B64 &sk)
{
    B64 d;
    gf p[4];

    randombytes(sk.p(), 32);
    crypto_hash(d, sk);
    d[0] &= 248;
    d[31] &= 127;
    d[31] |= 64;

    scalarbase(p,d);
    pack(pk,p);

    FOR(i,32) {
        sk[32 + i] = pk[i];
        CHKSIZE(32+i);
    }}, sk);

    return 0;
}

static constexpr u64 L[32] = {0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10};

sv modL(B64 &r,i64 x[64])
{
    i64 carry,i,j;
    for (i = 63; i >= 32; --i) {
        carry = 0;
        for (j = i - 32; j < i - 12; ++j) {
            x[j] += carry - 16 * x[i] * L[j - (i - 32)];
            carry = (x[j] + 128) >> 8;
            x[j] -= carry << 8;
        }
        x[j] += carry;
        x[i] = 0;
    }
    carry = 0;
    FOR(j,32) {
        x[j] += carry - (x[31] >> 4) * L[j];
        carry = x[j] >> 8;
        x[j] &= 255;
    }},r);
    FORu(j,32) {
        x[j] -= carry * L[j];
    ENDu;
    FOR(i,32) {
        x[i+1] += x[i] >> 8;
        r[i] = x[i] & 255;
    }}, r);
}

sv reduce(B64 &r)
{
    i64 x[64];
    FOR(i,64) {
        x[i] = (u64) r[i];
    }},r);
    FOR(i,64) {
        r[i] = 0;
    }},r);
    modL(r,x);
}


static inline int crypto_sign(Message &sm, const Message &m, const Key & sk)
{
    B64 d,h,r;
    C<i64, 64> x;
    gf p[4];

    crypto_hash(d, sk);
    d[0] &= 248;
    d[31] &= 127;
    d[31] |= 64;

    sm.n = m.n+64;
    FORn(i,m.n) sm.p[64 + i] = m.p[i];
    FORu(i,32) {
        sm[32 + i] = d[32 + i];
    ENDu;

    crypto_hash(r, sm+32, sm.n+32);
    reduce(r);
    scalarbase(p,r);
    Key ksm = Key::wrap(sm.p);
    pack(ksm,p);

    FORu(i,32) {
        sm[i+32] = sk[i+32];
    ENDu;
    crypto_hash(h,sm,m.n + 64);
    reduce(h);

    FOR(i,64) {
        x[i] = 0;
    }},x);
    FOR(i,32) {
        x[i] = (u64) r[i];
    }},x);
    FOR(i,32) {
        FOR2(j,32,i) {
            x[i+j] += h[i] * (u64) d[j];
            CHKSIZE(i+j);
        }},x);
    }},x);
    B64 sms = B64::wrap(sm.p + 32);
    modL(sms,x.p());

    return 0;
}


si unpackneg(gf r[4],const Key p)
{
    gf t, chk, num, den, den2, den4, den6;
    set25519(r[2],gf1);
    unpack25519(r[1],p);
    S(num,r[1]);
    M(den,num,D);
    Z(num,num,r[2]);
    A(den,r[2],den);

    S(den2,den);
    S(den4,den2);
    M(den6,den4,den2);
    M(t,den6,num);
    M(t,t,den);

    pow2523(t,t);
    M(t,t,num);
    M(t,t,den);
    M(t,t,den);
    M(r[0],t,den);

    S(chk,r[0]);
    M(chk,chk,den);
    if (neq25519(chk, num)) M(r[0],r[0],I);

    S(chk,r[0]);
    M(chk,chk,den);
    if (neq25519(chk, num)) return -1;

    if (par25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]);

    M(r[3],r[0],r[1]);
    return 0;
}

si crypto_sign_open(Message &msg, const Message &smsg, const Key &pk)
{
    Key t;
    B64 h;
    gf p[4],q[4];

    msg.n = -1;
    u64 n= smsg.n;
    if (n < 64) return -1;

    if (unpackneg(q,pk)) return -1;

    u8* m = msg.p;
    u8* sm = smsg.p;
    FORn(i,n) {
        m[i] = sm[i];
    }
    FORu(i,32) {
        m[i+32] = pk[i];
    ENDu;
    crypto_hash(h,msg,n);
    reduce(h);
    scalarmult(p,q,h);

    scalarbase(q, B64::wrap(sm + 32));
    add(p,q);
    pack(t,p);

    n -= 64;
    if (crypto_verify(Key::wrap(sm), t)) {
        FORn(i,n) {
            m[i] = 0;
        }
        return -1;
    }

    FORn(i,n) {
        m[i] = sm[i + 64];
    }
    msg.n = n;
    return 0;
}
